/LMAR=0/XLINE=3/FONT#0=BAXL30/FONT#1=BAXM30/FONT#2=BASB30/FONT#3=SUB/FONT#4=SUP/FONT#5=BASL35/FONT#6=NGR25/FONT#7=MATH30/FONT#8=FIX25



␈↓ α∧␈↓α␈↓ β#PATTERN DIRECTED COMPUTATION AND PROBLEM SOLVING

␈↓ α∧␈↓␈↓ αTThis␈α∩is␈α∩a␈α∩preliminary␈α∩report␈α∩on␈α∪an␈α∩investigation␈α∩that␈α∩has␈α∩changed␈α∩its␈α∩character␈α∪as␈α∩it
␈↓ α∧␈↓proceeded.␈α Since␈αI␈αam␈αnot␈αsure␈αwhere␈αit␈αwill␈αfinish,␈αI'll␈αstart␈αwith␈αthe␈αproblem␈αas␈αoriginally␈αposed
␈↓ α∧␈↓and show how several stages of generalization have led to its present state.

␈↓ α∧␈↓␈↓ αTWe␈α∪begin␈α∪with␈α∪what␈α∪we␈α∪call␈α∪␈↓↓syntax-directed␈α∪computation␈↓␈α∪which␈α∪we␈α∪will␈α∪generalize␈α∩to
␈↓ α∧␈↓␈↓↓pattern-directed␈αcomputation␈↓␈α
although␈αsyntactic␈αpatterns␈α
will␈αremain␈αan␈α
important␈αcase.␈α The␈α
term
␈↓ α∧␈↓␈↓↓syntax-directed␈α⊂computation␈↓␈α⊂is␈α∂itself␈α⊂a␈α⊂generalization␈α∂of␈α⊂␈↓↓syntax-directed␈α⊂compiling␈↓␈α⊂and␈α∂␈↓↓syntax-
␈↓ α∧␈↓↓directed input-output␈↓.

␈↓ α∧␈↓␈↓ αTThe␈αidea␈α
of␈αsyntax-directed␈α
computation␈αis␈α
quite␈αsimple␈α
and␈αquite␈α
old.␈α It␈α
is␈αquite␈α
tempting,
␈↓ α∧␈↓for␈α∂example,␈α⊂to␈α∂try␈α∂to␈α⊂describe␈α∂differentiation␈α⊂and␈α∂algebraic␈α∂simplification␈α⊂with␈α∂a␈α⊂collection␈α∂of
␈↓ α∧␈↓rules like

␈↓ α∧␈↓␈↓ αT␈↓↓D(u + v) → Du + Dv␈↓

␈↓ α∧␈↓and

␈↓ α∧␈↓␈↓ αT␈↓↓u + 0 → u␈↓.

␈↓ α∧␈↓We␈α
will␈α
work␈αin␈α
the␈α
framework␈αof␈α
LISP,␈α
for␈α
reasons␈αthat␈α
will␈α
become␈αapparent␈α
and␈α
which␈αare␈α
not
␈↓ α∧␈↓merely parochial, so the above transformations become

␈↓ α∧␈↓␈↓ αT(DIFF (PLUS U V)) → (PLUS (DIFF U) (DIFF V))

␈↓ α∧␈↓and

␈↓ α∧␈↓␈↓ αT(PLUS U 0) → U.

␈↓ α∧␈↓At␈α
first␈α
sight␈α
it␈α
seems␈α
more␈α
pleasant␈α
to␈α
write␈αsuch␈α
rules␈α
than␈α
to␈α
write␈α
programs␈α
in␈α
LISP␈α
or␈αany
␈↓ α∧␈↓other␈α⊂programming␈α⊂language,␈α⊂and␈α⊂so␈α⊂many␈α∂languages␈α⊂and␈α⊂packages␈α⊂within␈α⊂such␈α⊂languages␈α∂as
␈↓ α∧␈↓LISP␈α∂have␈α∂been␈α∞written␈α∂that␈α∂interpret␈α∞collections␈α∂of␈α∂transformation␈α∞rules␈α∂or␈α∂compile␈α∂them␈α∞into
␈↓ α∧␈↓program.

␈↓ α∧␈↓␈↓ αTOne␈α↔immediate␈α_question␈α↔is␈α↔whether␈α_there␈α↔is␈α↔any␈α_limit␈α↔on␈α↔what␈α_can␈α↔be␈α_done␈α↔by
␈↓ α∧␈↓transformation␈α⊗rules␈α⊗or␈α⊗whether␈α⊗any␈α⊗computable␈α⊗function␈α⊗of␈α⊗symbolic␈α⊗expressions␈α⊗can␈α∃be
␈↓ α∧␈↓computed␈α∩by␈α∩such␈α∩a␈α⊃system.␈α∩ The␈α∩answer␈α∩has␈α∩been␈α⊃known␈α∩since␈α∩the␈α∩1930s;␈α∩any␈α⊃computable
␈↓ α∧␈↓function␈αcan␈αbe␈αcomputed␈αby␈αa␈αPost␈αcanonical␈αsystem␈αwhich␈αis␈αone␈αsystem␈αfor␈αwriting␈αsuch␈αrules.
␈↓ α∧␈↓However,␈α∩the␈α⊃proof␈α∩involves␈α⊃using␈α∩such␈α∩rules␈α⊃to␈α∩simulate␈α⊃a␈α∩universal␈α⊃Turing␈α∩machine␈α∩or␈α⊃a
␈↓ α∧␈↓computer␈αor␈αto␈αmake␈αa␈αset␈αof␈α
rules␈αconstituting␈αan␈αinterpreter␈αfor␈αsome␈αprogramming␈αlanguage.␈α
 It
␈↓ α∧␈↓is␈α⊗entirely␈α↔clear␈α⊗that␈α↔there␈α⊗is␈α↔no␈α⊗programming␈α↔or␈α⊗practical␈α↔advantage␈α⊗in␈α↔writing␈α⊗syntax
␈↓ α∧␈↓transformation␈α∂rules␈α∞to␈α∂simulate␈α∞a␈α∂program.␈α∞ Therefore,␈α∂the␈α∞question␈α∂of␈α∞what␈α∂computations␈α∞are
␈↓ α∧␈↓conveniently␈αdone␈αby␈αsets␈αof␈αsyntax␈αtransformation␈αrules␈αremains.␈α The␈αpractical␈αsystems␈αall␈αallow
␈↓ α∧␈↓the␈α∂admixture␈α∂of␈α∂conventional␈α∂computation␈α∂in␈α∂one␈α∂way␈α∂or␈α∂another,␈α∂and␈α∂programmers␈α⊂in␈α∂these
␈↓ α∧␈↓languages make frequent though often obscure use of these facilities.



␈↓ α∧␈↓␈↓ ε|1␈↓ ∧



␈↓ α∧␈↓␈↓ αTThese␈αpractical␈αlanguages␈αinclude␈αCOMIT␈α(early␈αbut␈αdefunct),␈αSNOBOL␈α(widely␈αused,␈αbut
␈↓ α∧␈↓rarely␈α∩for␈α∩heavy␈α∩computation)␈α∩and␈α∩various␈α⊃packages␈α∩in␈α∩LISP␈α∩such␈α∩as␈α∩METEOR␈α∩(early␈α⊃but
␈↓ α∧␈↓defunct) and

␈↓ α∧␈↓␈↓ αTThe␈αidea␈αis␈αthat␈αinstantiation␈αis␈αa␈αspecial␈αcase␈αof␈αpattern␈αrecognition␈αwhich␈αis␈αa␈αspecial␈αcase
␈↓ α∧␈↓of␈α∀problem␈α∀solving.␈α∀ We␈α∀start␈α∀with␈α∀the␈α∀LISP␈α∀function␈α∀␈↓↓inst␈↓␈α∀which␈α∀does␈α∀a␈α∀simple␈α∃form␈α∀of
␈↓ α∧␈↓instantiation␈αand␈α
generalize␈αit␈α
in␈αstages␈α
to␈αa␈αproblem␈α
solver␈αfor␈α
a␈αcertain␈α
class␈αof␈α␈↓↓obvious␈↓␈α
problems.
␈↓ α∧␈↓In the present draft, it is not yet clear what our notion of ␈↓↓obvious␈↓ shall be.

␈↓ α∧␈↓␈↓ αTWe begin with

␈↓ α∧␈↓␈↓ αT␈↓↓inst[pat,expr,a] ←
␈↓ α∧␈↓␈↓ αT                ␈↓αif␈↓ a ␈↓αeq␈↓ NO␈↓↓ ␈↓αthen␈↓↓ ␈↓NO␈↓↓
␈↓ α∧␈↓↓␈↓ αT                ␈↓αelse␈↓↓ ␈↓αif␈↓↓ isvar pat
␈↓ α∧␈↓↓␈↓ αT                        ␈↓αthen␈↓↓ {assoc[pat,a]}[λz.
␈↓ α∧␈↓↓␈↓ αT                                ␈↓αif␈↓↓ ␈↓αn␈↓↓ z ␈↓αthen␈↓↓ [pat.expr].a
␈↓ α∧␈↓↓␈↓ αT                                ␈↓αelse␈↓↓ ␈↓αif␈↓↓ ␈↓αd␈↓↓ z ␈↓αeq␈↓↓ expr ␈↓αthen␈↓↓ a
␈↓ α∧␈↓↓␈↓ αT                                ␈↓αelse␈↓↓ ␈↓NO␈↓↓]
␈↓ α∧␈↓↓␈↓ αT                ␈↓αelse␈↓↓ ␈↓αif␈↓↓ ␈↓αa␈↓↓t pat ␈↓αthen␈↓↓ [␈↓αif␈↓↓ pat ␈↓αeq␈↓↓ expr ␈↓αthen␈↓↓ a ␈↓αelse␈↓↓ ␈↓NO␈↓↓]
␈↓ α∧␈↓↓␈↓ αT                ␈↓αelse␈↓↓ inst[␈↓αd␈↓↓ pat,␈↓αd␈↓↓ expr,inst[␈↓αa␈↓↓ pat,␈↓αa␈↓↓ expr,a]]]␈↓.

␈↓ α∧␈↓␈↓ αTHere␈α
␈↓↓pat␈↓␈α
is␈αa␈α
pattern␈α
such␈αas␈α
(PLUS␈α
X␈α
Y)␈αwhere␈α
we␈α
suppose␈αthat␈α
the␈α
predicate␈α␈↓↓isvar␈↓␈α
knows
␈↓ α∧␈↓that␈α
X␈α
and␈αY␈α
are␈α
variables␈αand␈α
PLUS␈α
is␈α
not.␈α ␈↓↓expr␈↓␈α
is␈α
an␈αexpression,␈α
for␈α
example␈α(PLUS␈α
(TIMES
␈↓ α∧␈↓A␈α
B)␈α
C),␈αand␈α
␈↓↓a␈↓␈α
is␈α
an␈αa-list,␈α
i.e.␈α
a␈α
list␈αof␈α
dotted␈α
pairs,␈αeach␈α
of␈α
which␈α
is␈αa␈α
variable␈α
paired␈α
with␈αa
␈↓ α∧␈↓value.  ␈↓↓inst␈↓ is usually called with ␈↓↓a_=_NIL␈↓, and we have

␈↓ α∧␈↓␈↓ αT␈↓↓inst[␈↓(PLUS_X_Y),(PLUS_(TIMES_A_B)_C),NIL]_=_((X . (TIMES A B))(Y . C)).

␈↓ α∧␈↓In␈αgeneral,␈αhowever,␈α␈↓↓a␈↓␈αgives␈αthe␈αcommitments␈αfor␈αthe␈αvariables␈αthat␈αhave␈αalready␈αbeen␈αmade,␈α
and
␈↓ α∧␈↓this␈αis␈α
used␈αin␈αthe␈α
recursion.␈α The␈α
value␈αof␈α␈↓↓inst[pat,expr,a]␈↓␈α
is␈αthe␈α
a-list␈αof␈αcommitments␈α
required
␈↓ α∧␈↓to␈α∂make␈α⊂the␈α∂pattern␈α∂␈↓↓pat␈↓␈α⊂match␈α∂the␈α⊂expression␈α∂␈↓↓expr.␈↓␈α∂␈↓↓inst␈↓␈α⊂is␈α∂the␈α∂inverse␈α⊂of␈α∂the␈α⊂function␈α∂␈↓↓sublis␈↓
␈↓ α∧␈↓defined by

␈↓ α∧␈↓␈↓ αT␈↓↓sublis[a,pat] ← ␈↓αif␈↓↓ isvar pat ␈↓αthen␈↓↓ ␈↓αd␈↓↓ assoc[pat,a] ␈↓αelse␈↓↓ sublis[a,␈↓αa␈↓↓ pat].sublis[a,␈↓αd␈↓↓ pat]␈↓.

␈↓ α∧␈↓in the sense that

␈↓ α∧␈↓␈↓ αT␈↓↓inst[pat,expr,a] ≠ ␈↓NO␈↓↓ ⊃ sublis[inst[pat,expr,a],pat] = expr␈↓.


␈↓ α∧␈↓John McCarthy
␈↓ α∧␈↓Artificial Intelligence Laboratory
␈↓ α∧␈↓Computer Science Department
␈↓ α∧␈↓Stanford University
␈↓ α∧␈↓Stanford, California 94305

␈↓ α∧␈↓ARPANET: MCCARTHY@SU-AI


␈↓ α∧␈↓␈↓ ε|2␈↓ ∧



␈↓ α∧␈↓␈↓εThis draft PUBbed at 18:45 on November 15, 1976.␈↓
















































␈↓ α∧␈↓␈↓ ε|3␈↓ ∧